package 分治快排;

import java.util.Random;

public class 排序数组2 {
    //https://leetcode.cn/problems/sort-an-array/description/
    public int[] sortArray1(int[] nums) {
        partation(0,nums.length - 1, nums);
        return nums;
    }
    private void partation(int left, int right, int[] nums) {
        // 最后再写 已经排好 递归结束时 的情况
//        if(right == 0) return; // 左区间只有一个待排元素
//        if(left == nums.length - 1) return; // 右区间只有一个待排元素
        if(left >= right) return;
        Random random = new Random();
        int rand = random.nextInt();
        if(rand < 0) rand = -rand;
        int rand_index = rand % (right - left + 1) + left;
        int r = nums[rand_index];
        int left1 = left - 1, cur = left, right1 = right + 1;
        for(; cur < right1;) {
            if(nums[cur] < r) swap(++left1,cur++,nums);
            else if(nums[cur] > r) swap(--right1,cur,nums);
            else cur++;
        }
        // 排好一次中间块后，去剩下的左边块 去排块、剩下的右边块 去排块
        // left维护指向 包含左区间的最右端，right维护指向 包含右区间的最左端，cur维护指向 包含待排区间的最左端
//        partation(0,left1,nums);
//        partation(right1, nums.length - 1,nums);
        partation(left,left1,nums);
        partation(right1, right,nums);
    }
    public static void main(String[] args) {
        排序数组2 test = new 排序数组2();
        test.sortArray1(new int[] {5,2,3,1});
        int a = 10;
        for(;a > 0;) {
            a--;
        }
        for(int b = 3; b > 0; b--)
            ;
    }

    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }
    public void qsort(int[] nums, int l, int r) {
        if(l >= r) return;

        // 三指针法 数组分三块 排块基准
        int key = nums[new Random().nextInt(r - l + 1) + l]; // 3 -> [0,2]
        int left = l - 1, right = r + 1, cur = l;
        while (cur < right) {
            if(nums[cur] < key) swap(++left, cur++, nums);
            else if(nums[cur] == key) cur++;
            else swap(--right, cur, nums);
        }
        //左块性质<基准元素，中间第三块性质=基准元素->排好一块元素，右块性质>基准元素：

        // 一性质块：[l, left] < 基准元素(右边剩下是 >=基准元素),
        // 两剩性质块：[left + 1, right - 1] = 基准元素，左边小于它，右边大于它，排好了一块元素,
        // 一性质块：( 左边剩下是 <=基准元素)[right, r] > 基准元素
        qsort(nums, l, left);
        qsort(nums, right, r);
    }
    private void swap(int x, int y, int[]nums) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
}
